//2009/10/20 19:49:29
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

int inf = 210000000;
int dir[2][4] = {{0, 0, 1, -1}, {1, -1, 0, 0}};
class PizzaDelivery
{
public:
    int deliverAll(vector <string> terrain)
    {
        int ret = 0;
		//int temp = 0
        for (int i=0; i<terrain.size(); i++)
            for (int j=0; j<terrain[i].size(); j++)
                if (terrain[i][j] == '$')
                {
                    int temp = dfs(terrain, i, j);
                    if (temp == inf) return -1;
                    ret += temp;
                }
        return ret;
    }
    int dfs(vector<string> terrain, int x, int y)
    {
        int w[4] = {inf};
        if (terrain[x][y] == 'X') return 0;
		for(int i=0; i<4; i++)
		{
			int xx = x + dir[0][i];
			int yy = y + dir[1][i];
			if(isbound(terrain, xx, yy))
				if(cost(terrain, x, y, xx, yy) != -1)
					w[i] = cost(terrain, x, y, xx, yy) + dfs(terrain, xx, yy);
		}
		/*
        if (isbound(terrain, x-1, y))
        {
            if (cost(terrain, x, y, x-1, y) != -1)
                w1 = cost(terrain, x, y, x-1, y) + dfs(terrain, x-1, y);
        }
        else if (isbound(terrain, x+1, y))
        {
            if (cost(terrain, x, y, x+1, y) != -1)
                w2 = cost(terrain, x, y, x+1, y) + dfs(terrain, x+1, y);
        }
        else if (isbound(terrain, x, y+1))
        {
            if (cost(terrain, x, y, x, y+1) != -1)
                w3 = cost(terrain, x, y, x, y+1) + dfs(terrain, x, y+1);
        }
        else if (isbound(terrain, x, y-1))
        {
            if (cost(terrain, x, y, x, y-1) != -1)
                w4 = cost(terrain, x, y, x, y-1) + dfs(terrain, x, y-1);
        }
		*/
        return min(min(w[1], w[2]), min(w[3], w[0]));
    }
    bool isbound(vector<string> terrain, int x, int y)
    {
        if (x>=0 && x<terrain.size() && y>=0 && y<terrain[0].size())
            return true;
        return false;
    }
    int cost(vector<string> terrain, int x, int y, int x1, int y1)
    {
        if (terrain[x][y]=='X' || terrain[x1][y1]=='X' || terrain[x][y]=='$' || terrain[x1][y1]=='$') return 2;
        if (isdigit(terrain[x][y]) && abs(terrain[x][y]-terrain[x1][y1]) == 0) return 1;
        if (isdigit(terrain[x][y]) && abs(terrain[x][y]-terrain[x1][y1]) == 1) return 3;
        return -1;
    }
};
